<?php
/**
 * @title 31. 下一个排列 - 递归
 * @author start2004
 */

class Solution {

    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function nextPermutation(&$nums) {
        if(count($nums) == 1){
            return $nums;
        } else {}

        /**
         * @since 2020-07-03 检查是否降序排列
         */
        $len=count($nums);
        list($desc, $i) = self::isDesc($nums, 0, $len-1);

        /**
         * @since 2020-07-03 区分处理
         */
        if($desc){
            /**
             * @since 2020-07-03 完全降序, 反转即可
             *
             * 6,5,4,3,2,1
             */
            $nums = self::revArray($nums, 0, $len-1);
        } else {
            /**
             * @since 2020-07-03 不完全, 存在字典排序的下个组合
             * nums[i] 小于 nums[i+1]
             */
            $nums = self::nextDict($nums, $i, $len);
        }

        /**
         * @return
         */
        return $nums;
    }

    /**
     * @title 返回字典排序下一个组合
     * @author start2004
     * @since 2020-07-03 Created
     *
     * @param array $nums
     * @param int $i
     * @param int $len
     * @return array
     */
    function nextDict($nums = [], $i = 0, $len = 0){
        /**
         * @since 2020-07-03 非完全降序, 分界点i之后, 是否完全降序
         *
         * 4,5,2, 6,3,1
         *     ↑
         *     i
         */
        list($remainDesc, $j) = self::isDesc($nums, $i+1, $len-1);

        /**
         * @since 2020-07-03 完全降序, 找到比i大的最小元素
         *
         * 4,5,3, 6,2,1
         *     ↑    ↑
         *     i    k
         */
        if($remainDesc){
            /**
             * @since 2020-07-04 nums[i] 小于 nums[i+1], 在i节点之后,一定能找比i大的元素
             */
            for ($k=$len-1; $k>=0; $k--){
                if($nums[$k] > $nums[$i]){
                    list($nums[$i], $nums[$k]) = [$nums[$k], $nums[$i]];
                    break;
                } else {}
            }

            /**
             * @since 2020-07-03 i+到len-1部分, 完全降序, 改成升序
             * 4,5,3, 1,2,6
             *        ↑   ↑
             *      i+1   len-1
             */
            $nums = self::revArray($nums, $i+1, $len-1);
        } else {
            /**
             * @since 2020-07-03 并非完全降序
             *
             * 4,5,2, 3,8,7,6
             *        ↑
             *        j
             * 4,5,2, 6,3,7,8
             *
             * 非完全倒序
             * 4,5,2, 3,6,9,8,7
             *        ↑
             *        j
             * 4,5,2, 3,7,6,8,9
             */
            $nums = self::nextDict($nums, $j, $len);
        }

        /**
         * @return
         */
        return $nums;
    }

    /**
     * @title 反转数组某段
     * @author start2004
     * @since 2020-07-03 Created
     *
     * @param array $nums
     * @param int $left
     * @param int $right
     * @return array
     */
    function revArray($nums = [], $left = 0, $right = 0){
        while($left<$right){
            list($nums[$left], $nums[$right]) = [$nums[$right], $nums[$left]];
            $left++;
            $right--;
        }

        /**
         * @return
         */
        return $nums;
    }

    /**
     * @title 检查数组某段是否完全降序
     * @author start2004
     * @since 2020-07-03 Created
     *
     * @param array $nums
     * @param int $start
     * @param int $end
     * @return array
     */
    function isDesc($nums = [], $start = 0, $end = 0){
        $desc = true;

        for($i=$start, $iMax=$end-1; $i<=$iMax; $i++){
            if($nums[$i+1] > $nums[$i]){
                $desc = false;
                break;
            } else {}
        }

        /**
         * @return
         */
        return [$desc, $i];
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.03_4.php
 */
$datas = [
    [1,2,3],
    [3,2,1],
    [1,1,5],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->nextPermutation($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
